典型90問 036 - Max Manhattan Distance

問題の内容

$ N個の点$ (x_i, y_i)が与えられる

$ Q個のクエリ$ q_iが与えられる

それぞれのクエリに対して、$ q_i番目の点からのマンハッタン距離の最大値を求める

解説

「45度回転」というテクニックが使える。

それぞれの点を$ (u_i, v_i) = (x_i + y_i, x_i - y_i)で表す。

こうすると、$ i番目の点と$ j番目の点のマンハッタン距離は$ \max(|u_i - u_j|, |v_i - v_j|)となる。

$ uと$ vを独立に考えられるようになった。

それぞれのクエリの答えは、$ \max_j(|x_{q_i} - x_j| + |y_{q_i} - y_j|)である。

そのまま計算すると、クエリあたり$ O(N)になるので間に合わない。

$ (u, v) = (x + y, x - y)を使うと、$ \max_j \max(|u_{q_i} - u_j|, |v_{q_i} - v_j|)と表すことができる。

つまり、$ \max_j |u_{q_i} - u_j|と$ \max_j |v_{q_i} - v_j|のうち大きい方。

「$ u_{q_i}との差が最も大きい点はどれ？」→$ \min uまたは$ \max uのどちらか。

数直線上の点を考えると、自明。ある点から最も遠い点は左端か右端かのどちらか。

$ v_{q_i}についても、同様に考えることができる。

つまり、答えは$ \max(|u_{q_i} - \min u|, |u_{q_i} - \max u|, |v_{q_i} - \min v|, |v_{q_i} - \max v|)。

$ \min u, \max u, \min v, \max vはそれぞれ最初に計算しておくことで、前処理$ O(N)、クエリ$ O(1)で答えることができる。

コード

code:Ruby

N, Q = gets.split.map(&:to_i)

points = Array.new(N) { gets.split.map(&:to_i) }

queries = Array.new(Q) { gets.to_i - 1 }

u, v = [], []

points.each do |x, y|

u << x + y

v << x + y

end

u_min, u_max = u.minmax

v_min, v_max = v.minmax

queries.each do |q|

puts [(uq - u_min).abs, (uq - u_max).abs, (vq - v_min).abs, (vq - v_max).abs].max

end